目標：
這題主要目的在於引導讀者了解Linked List的資料結構以及基本操作。
原題：
Question:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
分析/解題：
題目要求將兩個已排序的linked lists合併，
且所產生的新list必須由原有的節點(node)所構成。
Linked List是一個很常見的資料結構，資料與資料連接的方式是單向的，
通常從第一個節點(node)往後連接到最後一個節點(node)。
每個節點上會存放一個(或一組)資料以及連結(link)，
每個連結會指向到下一個節點的位置(記憶體位址)。
(在C/C++裡面連結基本上就是指標(pointer))
你可能會問，那麼最後一個節點呢?
最後一個節點除了儲存資料以外，因為連結沒有東西了，所以會給定空值。
在演算法的書中一般會稱為NIL，NIL在英文裡面就是nothing的意思，
表示沒有任何東西。
在Java中有LinkedList的資料結構，它同樣是List的一種。
但一般遇到題目的時候會給的通常是一個node，
用來指向到該List的第一個節點。
我們會看到如果你打開LeetCode選擇Java時，
上方已經先用註解告訴你這個ListNode的結構了：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
也就是說，題目預先定義了一個class叫做ListNode，
val用來存放每個node的值，next用來指向到下一個node，
有一個**ListNode(int x)**的建構子(constructor)，
可以讓你在產生一個新的節點時給定其值。
對於LinkedList來說，它最大的好處在於新增/刪除節點時相當方便。
例如現在有a->b，我想要加一個資料值為20的c節點，放在b後面的話，
以Java而言只需要:
ListNode b = a.next; // 因為一開始我們只知道a的位置而已XD
ListNode c = new ListNode(20);
b.next = c;
如果是插入在a跟b中間呢？也不難，
只是我們要先記住b，不然一旦沒有人記它，它就消失在時空裂縫中了(誤)
(會依照各自編譯器的規範，只是以我們而言是真的就沒辦法找到它了)
// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
a.next = c;
c.next = b;
請留意如果你調動了一些節點的順序，留意他們的next是否被妥善處理，
該被清空的請給定NIL。在Java中是用null來表示，而Python則是用None。
回到題目，我們該如何去合併排列好的兩個LinkedList呢？
這邊提供一個很簡單的遞迴思路。
(遞迴的概念，我們之後再專門做一篇相關的來講解)
我們合併兩個list的狀況目標還是要呈現排序好的樣子，
那麼怎麼排呢？
由於原先的list已經是排好的，
我們拿出最左邊的node比較，稱為l1跟l2。
l1是全空的狀況下，那其實答案就是l2(因為後面就不用繼續排了)，
反之l2是全空的話，答案就是l1。
那麼如果l1的值小於l2的值的話，那麼l1應該要當頭，
接下來我們要拿l1.next跟l2來做比較大小，比較小的，
就會是新的l1連接的下一個節點。
一直連接到最後，我們就可以得到合併好的list了！
相等的狀況因為題目沒有特別要求要分辨是l1還是l2的節點，
所以任取一個均可。
例：
l1: 1 -> 3 -> 5 ->8 ->10, l2: 2 -> 4 -> 4
1先跟2比，1比較小所以當頭(1) ->
3跟2比，2比較小(1->2) ->
3跟4比(1->2->3) ->
5跟4比(1->2->3->4) ->
5跟4比(1->2->3->4->4) ->
l2的部分已經空了，填入l1中5以後剩下的部分
(1->2->3->4->4-> 5 ->8 ->10)
寫成Java的程式如下。
Java:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
當然我們也可以用迴圈(迭代)的方法來解，
但這時候我們就要比較仔細的去處理節點間的關係了。
在Python中判斷是否為None可以使用if，
通過if的話節點就代表該節點是有值的，
你也可以加入not的關鍵字來處理你所需要的判斷式。
比如我可以用if not (l1 and l2)來表達其中一個以上是空的狀況，
並回傳不是None的那個node。
操作上，我們需要一個dummy node做為旁觀者，
讓它從頭到尾都只保持在同樣的位置，並指向到第一個節點。
接著我們定義一個節點叫做prev，
prev的next會指定給下一個比較過後較小的那個節點。
那麼，每次將prev的next拿到以後，
l1或l2(看哪個比較小)就自己遞移到下一個節點，
並且prev也往下走到自己的next，準備接取下一個節點；
重覆上面的動作直到其中一邊節點用光，
即可把剩下的直接全接到prev.next上。
最終我們回傳的答案是dum.next，因為只有dum沒有被動過，
其他的節點其實都已經被改動過指向的位址了。
Python:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dum = ListNode(None)
prev = dum
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
if l1 == None:
prev.next = l2
elif l2 == None:
prev.next = l1
return dum.next
在有關linked list的部分，因為牽扯到位址的概念，
所以操作上要稍微再思考一下，比較不容易搞混。
最重要的是，對於Java和Python來說，由於所使用的都是class來建立node，
所以你看到的等號，除了給定val的狀況以外，
其他其實都是在做把右邊放的記憶體位址存到左邊的動作，
所以指向的記憶體位址變了，代表的節點也就跟著變了，務必要留意這點。
面試實際可能會遇到的問題：
「請用iterative(迭代或迴圈)/recursive(遞迴)的方式來解」
(上面Java是recursive solution，Python是iterative solution，
讀者可以嘗試改成另一個語言試看看)
「使用遞迴的話會有什麼限制？」
(有可能受到編譯器規範的最大function stack上限限制，
同時，連續的函式呼叫的效率，相對於在迴圈中執行來說會較差)
「那為什麼你會用遞迴？」
(因為遞迴比較好想啊XDDDDD)(別這麼誠實，雖然大家都知道XD)
(因為在一般狀況下，遞迴解通常會較為容易閱讀，
也比較符合人類的思路模式，就像推骨牌一樣，
當起始條件和後續的脈絡定下來以後，後面的結果就會水到渠成。)
「時間複雜度是？」
( worst case是O(N1+N2)，best case是O(min(N1, N2))。)
「如果希望你另外開一個新的linked list，不用原本的節點來解這題呢？」
(這樣會比較簡單，一樣兩兩比較，
但改成較小的取其val來產生一個新的ListNode，
接在你的新的linked list後面，讀者可以嘗試看看，
別忘記要留dummy node歐！)
從LeetCode學演算法，我們下次見囉，掰~
下篇預告：
0026. Remove Duplicates from Sorted Array (Easy)
你好，請問這段code：
// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
a.next = c;
c.next = b;
似乎應該是：
// a -> c -> b
ListNode b = a.next;
ListNode c = new ListNode(20);
c.next = b;
a.next = c;
不然b可能就消失在時空裂縫了?
你好:
在理解next這件事情的時候，必須要知道一點是，
以物件而言，它所記錄或指向的都是該物件的記憶體位置，
而非整個值。
以Python而言，我們嘗試定義以下的ListNode，
並給定a, a.next, c，你可以試試看基本的直譯器，
來輸出ListNode的記憶體位置和其val:
>>> class ListNode:
... def __init__(self, x):
... self.val = x
... self.next = None
...
>>> a = ListNode(1)
>>> a.next = ListNode(3)
>>> b = a.next
>>> c = ListNode(20)
>>> a
<__main__.ListNode object at 0x0000000002838DA0>
>>> a, a.val
(<__main__.ListNode object at 0x0000000002838DA0>, 1)
>>> a.next, a.next.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> b, b.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> c, c.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>>
>>> a.next = c
>>> c.next = b
>>> b, b.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>> c, c.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>> a.next, a.next.val
(<__main__.ListNode object at 0x0000000002838B70>, 20)
>>> c.next, c.next.val
(<__main__.ListNode object at 0x0000000002838D68>, 3)
>>>
從上面來看，你會發現先做a.next = c而不是c.next = b的結果，
並不會讓b消失在時空裂縫。為什麼呢？
當我們在下a.next = c時，
我們所指涉的是
「將a.next的記憶體位址設定為c的記憶體位址」。
此時，由於我們先前已經有變數b來記錄b所在的記憶體位址，
所以這一行並不會讓b記錄的記憶體位置改變，
改變的只有a.next，b並沒有改變。
唯一會讓b找不到的狀況就是我們沒有宣告任何物件來存放這個物件。
類似：
a = ListNode(1)
a.next = ListNode(3) # 也就是b，但我們沒有宣告b來存
c = ListNode(20)
a.next = c # 將a的next指向到c的記憶體位址
# 這時候因為沒有人存ListNode(3)，所以它就再也存取不到了！
所以以這個簡短範例而言，
兩者的代換前後順序，並不會影響結果，
也不會有任何人陷入時空裂縫XD
iThome鐵人賽
看影片追技術